Started=false;
//上id#frameModalTopInfoDemo
//下id#fluidModalBottomDangerDemo
//上文本框id TopWarningContent
//下文本框 BottomDangerInfo
function TopHint(content)
{
    document.getElementById("TopWarningContent").innerHTML=content;
    $('#frameModalTopInfoDemo').modal();
}
function DownHint(content)
{
    document.getElementById("BottomDangerInfo").innerHTML=content;
    $('#fluidModalBottomDangerDemo').modal();
}

//下面开始源代码


function start(){
    Started=true;
    var $ = go.GraphObject.make;
     allnumber=0;
     myDiagram =
      $(go.Diagram, "div1",
        {
          "undoManager.isEnabled": false,
          initialAutoScale: go.Diagram.Uniform,
          contentAlignment: go.Spot.Center,
          layout: $(go.TreeLayout,
                    { angle: 90, layerSpacing: 35 })
        });
    
    
   myDiagram.nodeTemplate =
          $(go.Node, "Spot",
            { locationSpot: go.Spot.Center },
            new go.Binding("text", "text"),  // for sorting
            $(go.Shape, "Ellipse",
              {
                fill: "lightgray",  // the initial value, but data binding may provide different value
                stroke: null,
                desiredSize: new go.Size(30, 30)
              },
              //new go.Binding("desiredSize", "size"),
              new go.Binding("fill", "fill")),
            $(go.TextBlock,
              {stroke:"#FFFFFF"},
              new go.Binding("text", "lan"))
          );
    // define a Link template that routes orthogonally, with no arrowhead
    myDiagram.linkTemplate =
      $(go.Link,
        { routing: go.Link.Orthogonal, corner: 5 },
        $(go.Shape, // the link's path shape
          { strokeWidth: 1, stroke: "#708090" }));
    
    var model = $(go.TreeModel);
    model.nodeDataArray =
    [
      
    ];
  
    myDiagram.model = model;
   
     BinarySearchTree = function(){
      this.root = null;
      ///
  }
  
  
  BinarySearchTree.prototype = {
      insert: function(keyvalue){//插入
          var newNode = new this.Node(keyvalue);
          if(this.root === null){
              this.root = newNode;
          }
          else
          {
              this.insertNode(this.root, newNode)
          }
          console.log(this.root);
      },
      
      Node: function(key){
          this.key = key;
          this.left = null;
          this.right = null;
      },
      insertNode: function(node, newNode){
          if(newNode.key < node.key){
              if(node.left === null){
                  node.left = newNode;
                 
              }else{
                  this.insertNode(node.left, newNode)
              }
          }else{
              if(node.right === null)
              {
                  node.right = newNode;
                 
              }
              else{
                  this.insertNode(node.right, newNode)
              }
          }
      },
     
      minNode: function(node){
          if(node){
              while(node && node.left !== null){
                  node = node.left;
              }
              return node.key;
          }
          return null;
      },
      maxNode: function(node){
          if(node){
              while(node && node.right !== null){
                  node = node.right;
              }
              return node.key;
          }
          return null;
      },
      searchNode: function(node, key){//bool type and only return for it true and false 
          if(node === null)
          return false;
          if(key < node.key){
              return this.searchNode(node.left, key);
          }else if(key > node.key){
              return this.searchNode(node.right, key);
          }else{
              return true;
          }
      },
      
      findMinNode: function(node){
          if(node){
              while(node && node.left !== null){
                  node = node.left;
              }
              return node.key;
          }
          return null;
      },
      deleteWithKey:function(key)
      {
          this.deleteNodeWithKey(this.root,null,false,key);
      },
      deleteNodeWithKey:function(node,parnode,whetherleftin,key)
      {
          if(node.key==key)
          {
              if(node.left==null&&node.right==null)//被删除节点正好为叶子结点
              {
                  if(parnode!=null)
                  {
                      if(whetherleftin)
                      parnode.left=null;
                      else
                      parnode.right=null;
                  }
                 
                  node=null;
                  
                  return 1;
              }
              if(node.left==null)//被删除的节点只有右侧有子树
              {
                  if(node==this.root)
                  {
                    this.root.key=node.right.key;
                      this.root.left=node.right.left;
                      this.root.right=node.right.right;
                  }
                  else
                  {
                  if(whetherleftin)
                  {
                      parnode.left=node.right;
                  }
                  else
                  {
                  parnode.right=node.right;
                  }
                }   
                  node=null;
                  return 1;
              }
              if(node.right==null)//被删除的节点只有左子树
              {
                  if(node==this.root)
                  {
                      this.root.key=node.left.key;
                      this.root.left=node.left.left;
                      this.root.right=node.left.right;
                  }
                  else
                  {
                      if(whetherleftin)
                      parnode.left=node.left;
                    else
                        parnode.right=node.left;
                  }
                 
                  node=null;
                  return 1;
              }
              var mxskey=this.minNode(node.right);
              this.deleteNodeWithKey(node.right,node,false,mxskey);
              node.key=mxskey;
          }
          else
          {
              if(node.key>key)
              {
                  if(node.left!=null)
                   this.deleteNodeWithKey(node.left,node,true,key);
                  else
                  return 0; 
              }
              else
              if(node.right!=null)
                  this.deleteNodeWithKey(node.right,node,false,key);
              else
              return 0;    
          }
      },
      drawinto_bst:function(){
          myDiagram.model.addNodeData({key:this.root.key.toString(),lan:this.root.key.toString(),fill:"#7B86EE"});
          this.drwa_base(this.root);
      },
      drwa_base:function(node)
      {
          if(node.left!=null)
          {
              myDiagram.startTransaction("make new node");
              myDiagram.model.addNodeData({key:node.left.key.toString(),parent:node.key.toString(),lan:node.left.key.toString(),fill:"#7B86EE"});
              myDiagram.commitTransaction("make new node");
              this.drwa_base(node.left);
          }
          else
          {
              myDiagram.startTransaction("make new node");
          myDiagram.model.addNodeData({key:allnumber.toString(),parent:node.key.toString(),lan:"",fill:"#40e0d0"});
          myDiagram.commitTransaction("make new node");
          allnumber=allnumber+1;
          }
          if(node.right!=null)
          {
              myDiagram.startTransaction("make new node");
              myDiagram.model.addNodeData({key:node.right.key.toString(),parent:node.key.toString(),lan:node.right.key.toString(),fill:"#7B86EE"});
              myDiagram.commitTransaction("make new node");
              this.drwa_base(node.right);
          }
          else
          {
              myDiagram.startTransaction("make new node");
          myDiagram.model.addNodeData({key:allnumber.toString(),parent:node.key.toString(),lan:"",fill:"#40e0d0"});
          myDiagram.commitTransaction("make new node");        
          allnumber=allnumber+1;
          }
  }
  }
    mybst=new BinarySearchTree();
    
    
   
   
  }
  function cleardata()
    {
        allnumber=0;
        while(myDiagram.model.nodeDataArray.length!=0)
        { myDiagram.startTransaction("remove node");
            myDiagram.model.removeNodeData(myDiagram.model.nodeDataArray[0]);
            myDiagram.commitTransaction("remove node")
        }
    }
    function refreshbst(){
          cleardata();
      mybst.drawinto_bst();
    }
  var butt1=document.getElementById("InitDiagram");
butt1.onclick=function()
{
    start();
    TopHint("已经成功生成了节点，请试试增加或删除节点！");
    //console.log("已经1000%了");
}
var inhelp1=document.getElementById("AddNodes");
var inhelp2=document.getElementById("RemoveNodes");
inhelp1.onclick=function()
{
    if(!Started)
        {
            DownHint("尚未初始化，请在页面顶端初始化");
            kuang1.value="";
            return;
        }
    var kuang1=document.getElementById("AddInputs");
    var innum=parseInt(kuang1.value);
    
    if(mybst.searchNode(mybst.root,innum))
        DownHint("该节点已经存在，无法重复添加！");
    else
        {
            TopHint("已经添加该节点");
        mybst.insert(innum);
    }

    kuang1.value="";
    refreshbst();
}
inhelp2.onclick=function()
{
    if(!Started)
        {
            DownHint("尚未初始化，请在页面顶端初始化");
            kuang2.value="";
            return;
        }
    var kuang2=document.getElementById("RemoveInputs");
    var innu=parseInt(kuang2.value);
    
    if(!mybst.searchNode(mybst.root,innu))
        DownHint("没有该节点，不能进行删除！");
    else
        {
            TopHint("已经删除了该节点");    
        mybst.deleteWithKey(innu);
        }
    kuang2.value="";
    refreshbst();
}